package violentRecursion;

/*
 *@description
 *@author hkfan
 *@version 1.0
 *@create 2025/5/26 15:07
 */
public class LeetCode_122 {
    public int maxProfit(int[] prices) {
        return solution_1(prices,0,0,false);
    }

    /**
     * @description 暴力递归
     * @author hkfan
     * @return int
     * @time 2025/5/26 15:18
     */
    private int solution_1(int[] prices, int i, int cur, boolean flag) {
        if (i>=prices.length){
            return cur;
        }
        if (flag){
            return Math.max(
                    solution_1(prices,i+1,cur+prices[i],false),
                    solution_1(prices,i+1,cur,true)
            );
        }else{
            return Math.max(
                    solution_1(prices,i+1,cur-prices[i],true),
                    solution_1(prices,i+1,cur,false)
            );
        }
    }

    /**
     * @description 动态规划
     * @author hkfan
     * @return int
     * @time 2025/5/26 15:18
     */
    private int solution_2(int[] prices, int index, int cur,  boolean flag){
        //1. 定义dp数组
        int[][] dp = new int[prices.length+1][2];
        //2. 动态规划
        for (int i = prices.length-1; i >= 0 ; i--) {
            dp[i][1]=Math.max(dp[i+1][0]+prices[i],dp[i+1][1]);
            dp[i][0]=Math.max(dp[i+1][1]-prices[i],dp[i+1][0]);
        }
        return dp[0][0];

    }


}
